package com.wfm.leetcode.editor.cn;

import java.util.*;

/**
 * 题意：就是把eat tea 分为一组 nat tan 一组 bat 一组
 * char->num   'a'+0
 * num->char   (char)97
 * abc->012    'b'-'a'
 */
public class PFour9字母异位词分组{
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    // 排序作为键
    // 时间 o(n*klogk) 空o(nk) n个数，k字符串最大长度
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> map = new HashMap<>();
        for (int i = 0; i < strs.length; i++) {
            String str = strs[i];
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String key = Arrays.toString(chars);
            List<String> list = map.getOrDefault(key, new ArrayList<>());
            list.add(str);
            map.put(key,list);

        }
        return new ArrayList<>(map.values());
    }

    // 计数作为键
    //时间 o(n*(k+26)) 空o(n(k+26)) n个数，k字符串最大长度
    //时间复杂度：O(n(k+∣Σ∣))，
    // 其中n是strs中的字符串的数量，
    // k是strs中的字符串的的最大长度，
    // Σ是字符集，在本题中字符集为所有小写字母，
    // ∣Σ∣=26。需要遍历n个字符串，对于每个字符串，需要O(k)的时间计算每个字母出现的次数，
    // O(∣Σ∣)的时间生成哈希表的键，以及O(1)的时间更新哈希表，因此总时间复杂度是O(n(k+∣Σ∣))。
    //空间复杂度：O(n(k+∣Σ∣))，其中n是strs中的字符串的数量，
    // k是strs中的字符串的最大长度，Σ是字符集，在本题中字符集为所有小写字母，
    // ∣Σ∣=26。需要用哈希表存储全部字符串，而记录每个字符串中每个字母出现次数的数组需要的空间为O(∣Σ∣)，
    // 在渐进意义下小于O(n(k+∣Σ∣))，可以忽略不计。

    public List<List<String>> groupAnagrams1(String[] strs) {
        HashMap<String, List<String>> map = new HashMap<>();
        for (int i = 0; i < strs.length; i++) {
            String str = strs[i];
            int[] m = new int[26];
            for (int j = 0; j < str.length(); j++) {
                char c = str.charAt(j);
                m[c-'a']++;
            }
            // 构建key，把上面for循环添加的下标不为1的字符找出来
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < m.length; j++) {
                while (m[j]!=0){
                    sb.append((char)('a'+j));
                    m[j]--;
                }
            }
            String key = sb.toString();
            List<String> list = map.getOrDefault(key, new ArrayList<>());
            list.add(str);
            map.put(key,list);

        }
        return new ArrayList<>(map.values());
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) { 
        Solution solution = new PFour9字母异位词分组().new Solution();
        System.out.println('a'+0);
    }

    public void test(){
        HashMap<String ,String> m = new HashMap<>();
        Set<String> keys = m.keySet();
        Collection<String> values = m.values();
    }
}